Rearrange String k Distance Apart

Given a non-empty string str and an integer k, rearrange the string such that the same characters are at least distance k from each other.

All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string “”.

Example 1:

  1. str = "aabbcc", k = 3
  3. Result: "abcabc"
  5. The same letters are at least distance 3 from each other.

Example 2:

  1. str = "aaabc", k = 3 
  3. Answer: ""
  5. It is not possible to rearrange the string.

Example 3:

  1. str = "aaadbbcc", k = 2
  3. Answer: "abacabcd"
  5. Another possible answer is: "abcabcda"
  7. The same letters are at least distance 2 from each other.